#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
@author: TiagoBarriga Nº 6048
'''
import KDTree
import time
import pickle
import matplotlib.pyplot as plt
import random

def Main():
    
    
    print "######### Utilizando listas ligadas ##########"
    KDTree.Main()
    print "######### Arvore Binaria Sem Stack ##########"
   
    #lista de nos
    nos = [None for k in range(12)]
   
    #criação dos nós
    nos[0] = KDTree.Node(11, "Squall LionHeart")
    nos[1] = KDTree.Node(2, "Cloud Strife")
    nos[2] = KDTree.Node(14, "Erza Titania")
    nos[3] = KDTree.Node(1, "Ultimecia")
    nos[4] = KDTree.Node(7, "Alucard")
    nos[5] = KDTree.Node(15, "Ceras Victoria")
    nos[6] = KDTree.Node(5, "Renoa Heartilly")
    nos[7] = KDTree.Node(8, "Vicent Valentine")
    nos[8] = KDTree.Node(4, "Rurouni Kenshin")
    nos[9] = KDTree.Node(4, "Solid Snake")
    nos[10] = KDTree.Node(4, "Sephiroth")
    nos[11] = KDTree.Node(4, "Brandon Heat")
    arv = KDTree.ArvorePesquisaBinaria()
   
    #adicionar os nos criados à arvore
    
    tempoNo = []   ##onde fica guardado o tempo que levou a preenxer a lista em cada no
    qtNos = []
    
    for k in range(1, 12):
        t1 = time.clock()
        arv.insert(nos[k])
        t2 = time.clock()
        tempoNo.append( t2 - t1)
        qtNos.append(k)
    pass
    print arv
    
    #imprimir a arvore, ja ordenada
    print "######## Arvore Ordenada #######"
    lista = []
    arv.inorder_walk(arv.root, lista)
    for x in lista:
        print x
    
    #Eliminar arvore RedBlack
    print
    print "Del"
    arv.delete(nos[3])    
    #imprimir a arvore ja com actualizada
    print "INORDER"
    lista = []
    arv.inorder_walk(arv.root, lista)
    for x in lista:
        print x
       
    #Fazer a pesquisa por Numero
    t1 = time.clock()
    print "PESQUISA por numero"
    print arv.search(arv.root, 5)
    t2 = time.clock()
    print "tempo gasto na pesquisa foi de: "
    print t2 - t1
    pass
   
    #procurar vizinhos 
    t1 = time.clock()
    print "PESQUISA por um vizinho "
    print arv.searchNeighbor(arv.root, 5)
    t2 = time.clock()
    print "tempo gasto na pesquisa foi de: "
    print t2 - t1
    
    pass
    print "MINIMO"
    print arv.minimum(arv.root)
   
    print "MAXIMO"
    print arv.maximum(arv.root)
   
    print "SUCESSOR"
    print arv.sucessor(nos[7])

    

################################ Necessario abilitar unicode para os acentos #######################################
    plt.xlabel("quantidade de Nos da arvore")
    plt.ylabel("tempo da criacao dos nos na arvore")
    plt.title("Ration (tempo nos)")
###########################################################################################
    ## desenho do grafico de do ratio do tempo

# teste de grafico com random
#
#    for k in range(0, 10000, 400):
#        for x in range(0, k, 100):
#            rand = random.randint(0, 100)
#            rand2 = random.randint(0, 100)
#        t1 = time.clock()
#        arv.insert(nos[k])
#        t2 = time.clock()
#        tempoNo.append( t2 - t1)
#    pass
    
    
    graf = plt.plot(qtNos, tempoNo, 'Dg')
    plt.grid(True)
    plt.savefig('Ration.png')
    plt.show()
 
Main()

